So sánh giữa 2 thuật toán dijkstra và Floyd-Warshall Thuật_toán_Floyd-Warshall

Thuật toán Dijkstra bình thường có 2 vòng lặp lồng nhau sẽ có Độ phức tạp thuật toán là O ( n 2 ) {\displaystyle O(n^{2})} .Thuật toán Floyd–Warshall bình thường có 3 vòng lặp lồng nhau sẽ có Độ phức tạp thuật toán là O ( n 3 ) {\displaystyle O(n^{3})} .

Dijsktra Floyd-Warshall
Ưu điểmChi phí thấp hơn Thuật toán Floyd–WarshallKhông cần chạy lại Thuật toán (có nghĩa là có tính kế thừa từ đường đi lẫn nhau)

Có thể chạy được với trọng số âm.

Nhược điểmKhông chạy được với trọng số âm.Chi phí cao O ( n 3 ) {\displaystyle O(n^{3})} cho mỗi cặp đỉnh